package jzoffer.q0301duplicatearray;

/**
 * Author:   dengxin
 * Date:     2020/4/18 11:12 上午
 *
 * 题目：
 * 在一个长度为n的数组里的所有数字都在[0,n-1]的范围内，数组中某些数字是重复的，
 * 但不知道有几个数字重复了，也不知道每个数字重复了几次，请找出数组中任意一个重复的数字
 *
 * 例：
 * 输入长度为7的数组：[2,3,1,0,2,5,3]
 * 输出：重复的数字2或3
 *
 * 第一版
 */
public class DuplicateArray1 {

    static int[] array1 = new int[]{2,3,1,0,2,5,3};
    static int[] array2 = new int[]{2,3,1,0,4,5,6};

    private static void findDuplicate(int[] source) {
        int n = source.length;
        for(int i=0; i<n; ) {
            int m = source[i];
            if (m != i) {
                if (source[i] != source[m]) {
                    source[i] = source[i] + source[m];
                    source[m] = source[i] - source[m];
                    source[i] = source[i] - source[m];
                } else {
                    System.out.println("Duplicate Num is " + m);
                    break;
                }
            } else {
                i++;
            }
        }
    }

    public static void main(String[] args) {
//        Duplicate1.findDuplicate(array1);
        DuplicateArray1.findDuplicate(array2);
    }

}
